package com.bwt.sort;

import java.util.Arrays;

public class RadixSort {
	public static void main(String[] args) {
		//int[] arr = {53, 3, 542, 748, 14, 214};

		int[] arr = new int[8000000];
		for(int i = 0;i < 8000000;i++){
			arr[i] = (int)(Math.random() * 80000);	//自动生成[0,80000)之间的随机数
		}
		long time = System.currentTimeMillis();
		radixSort2(arr);
		System.out.println(System.currentTimeMillis()- time);
		//1144
	}

	public static void radixSort2(int[] arr) {
		//假设第一个数就是最大数
		int max = arr[0];
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		//得到最大数是几位数
		int maxLength = (max + "").length();

		int[][] bucket = new int[10][arr.length];
		int[] bucktElementCounts = new int[10];

		for (int l = 0, n = 1; l < maxLength; l++, n *= 10) {
			//针对每个元素的位数进行排序, 第一次个位 ,第二次是十位 依次类推
			for (int j = 0; j < arr.length; j++) {
				//取出每个元素的个位
				int digitOfElement = arr[j] / n % 10;
				bucket[digitOfElement][bucktElementCounts[digitOfElement]] = arr[j];
				bucktElementCounts[digitOfElement] += 1;
			}
			//按照这个桶的顺序(一维数组的下标依次取出数据,放入原来的数组)
			int index = 0;
			//遍历每个桶,并将桶中的数据放入到元素中
			for (int k = 0; k < bucket.length; k++) {
				//如果桶中有数据我们才放入桶
				if (bucktElementCounts[k] != 0) {
					//循环该桶,即第k个桶(即第k个一维数组),将数据放入
					for (int i = 0; i < bucktElementCounts[k]; i++) {
						arr[index] = bucket[k][i];
						index++;
					}
					bucktElementCounts[k] = 0;
				}
			}
			//System.out.println("第"+(l+1)+"轮排序后的结果====" + Arrays.toString(arr));

		}
	}

	//推导过程
	public static void radixSort(int[] arr) {
		//第一轮(针对每个元素的个位进行排序处理)

		//定义一个二维数组表示10个桶, 每个桶就是一个一维数组
		//说明
		//1. 二维数组包含10个一维数组
		//2. 为了防止放入数的时候数据溢出,则每个一个数组的大小为所排序数组的长度
		//3. 基数排序是使用空间换时间的经典算法
		int[][] bucket = new int[10][arr.length];
		//为了记录每个桶中,实际存放了多少个数据,定义一个一维数组记录各个桶放入的数据个数
		//bucktElementCounts[0], 就是记录bucket[0]这个桶放入数据的个数
		int[] bucktElementCounts = new int[10];

		for (int j = 0; j < arr.length; j++) {
			//取出每个元素的个位
			int digitOfElement = arr[j] % 10;
			bucket[digitOfElement][bucktElementCounts[digitOfElement]] = arr[j];
			bucktElementCounts[digitOfElement] += 1;
		}
		//按照这个桶的顺序(一维数组的下标依次取出数据,放入原来的数组)
		int index = 0;
		//遍历每个桶,并将桶中的数据放入到元素中
		for (int k = 0; k < bucket.length; k++) {
			//如果桶中有数据我们才放入桶
			if (bucktElementCounts[k] != 0) {
				//循环该桶,即第k个桶(即第k个一维数组),将数据放入
				for (int i = 0; i < bucktElementCounts[k]; i++) {
					arr[index] = bucket[k][i];
					index++;
				}
				bucktElementCounts[k] = 0;
			}
		}
		System.out.println("第一轮排序后的结果====" + Arrays.toString(arr));

		//第二轮

		for (int j = 0; j < arr.length; j++) {
			//取出每个元素的个位
			int digitOfElement = arr[j] / 10 % 10;
			bucket[digitOfElement][bucktElementCounts[digitOfElement]] = arr[j];
			bucktElementCounts[digitOfElement] += 1;
		}
		//按照这个桶的顺序(一维数组的下标依次取出数据,放入原来的数组)
		index = 0;
		//遍历每个桶,并将桶中的数据放入到元素中
		for (int k = 0; k < bucket.length; k++) {
			//如果桶中有数据我们才放入桶
			if (bucktElementCounts[k] != 0) {
				//循环该桶,即第k个桶(即第k个一维数组),将数据放入
				for (int i = 0; i < bucktElementCounts[k]; i++) {
					arr[index] = bucket[k][i];
					index++;
				}
				bucktElementCounts[k] = 0;
			}
		}
		System.out.println("第二轮排序后的结果====" + Arrays.toString(arr));

		//第三轮

		for (int j = 0; j < arr.length; j++) {
			//取出每个元素的个位
			int digitOfElement = arr[j] / 100 % 10;
			bucket[digitOfElement][bucktElementCounts[digitOfElement]] = arr[j];
			bucktElementCounts[digitOfElement] += 1;
		}
		//按照这个桶的顺序(一维数组的下标依次取出数据,放入原来的数组)
		index = 0;
		//遍历每个桶,并将桶中的数据放入到元素中
		for (int k = 0; k < bucket.length; k++) {
			//如果桶中有数据我们才放入桶
			if (bucktElementCounts[k] != 0) {
				//循环该桶,即第k个桶(即第k个一维数组),将数据放入
				for (int i = 0; i < bucktElementCounts[k]; i++) {
					arr[index] = bucket[k][i];
					index++;
				}
				bucktElementCounts[k] = 0;
			}
		}
		System.out.println("第三轮排序后的结果====" + Arrays.toString(arr));
		/*第一轮排序后的结果====[542, 53, 3, 14, 214, 748]
		第二轮排序后的结果====[3, 14, 214, 542, 748, 53]
		第三轮排序后的结果====[3, 14, 53, 214, 542, 748]*/
	}
}
